package 牛客网编程.剑指offer.斐波那契数列;

/**
 * create at 2018/10/21
 * author: suveng
 * email: suveng@163.com
 **/
public class Solution {
//    冗余计算
    public int Fibonacci(int n) {
        if(n<2){
            return n;
        }
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
//    减少冗余
    public int Fibonacci2(int n) {
        if(n<2){
            return n;
        }
        int[] src = new int[n+1];
        src[0]=0;
        src[1]=1;
        int m;
        for(int i=2;i<=n;i++){
            src[i]=src[i-1]+src[i-2];
        }
        return src[n];
    }
//    动态规划，减少空间
public int Fibonacci3(int n) {
    if(n<2){
        return n;
    }
    int nm1=1;
    int nm2=0;
    int now=0;
    while (n>=2){
        now=nm1+nm2;
        nm2=nm1;
        nm1=now;
        n--;
    }
    return now;
}

}
